package com.jxm.sort;

import java.util.Arrays;

/**
 * @Author: jxm
 * @Description: 归并排序api设计
 * @Date: 2022/6/9 16:08
 * @Version: 1.0
 */
public class Quick {

    private static Comparable[] assist;//归并所需要的辅助数组

    /**
     * 对数组内的元素进行排序
     * @param a
     */
    public static void sort(Comparable[] a){
        int lo = 0;
        int hi = a.length - 1;
        sort(a,lo,hi);
    }

    /**
     * 对数组a中从索引lo到索引hi之间的元素进行排序
     * @param a
     * @param lo
     * @param hi
     */
    private static void sort(Comparable[] a, int lo, int hi){
        //做安全检查
        if(hi <= lo){
            return;
        }
        //需要对数组中lo索引到hi索引必的元素进行分组（左子组和右子组）
        int partition = partition(a, lo, hi); //返回的是分组的分界值所在的索引，分界值位置变换后的索引

        //让左子组有序
        sort(a,lo,partition-1);

        //让右子组有序
        sort(a,partition+1,hi);


    }

    /**
     * 对数组a中，从索引lo到索引hi之间的元素进行分组，并返回分组界限对应的索引
     * @param a
     * @param lo
     * @param hi
     */
    private static int partition(Comparable[] a, int lo, int hi){
        //确定分界值
        Comparable key = a[lo];
        //定义两个指针，分别指向待切分元素的最小索引处和最大索引处的下一个位置
        int left = lo;
        int right = hi + 1;
        //切分
        while (true){
            //先从右往左扫描，移动right指针，找到一个比分界值小的元素，停止
            while (less(key,a[--right])){
                if(right == lo){
                    break;
                }
            }
            //再从左往右扫描，移动eft指针，找到一个比分界值大的元素，停止
            while (less(a[++left],key)){
                if(left == hi){
                    break;
                }
            }

            //判断left>=right，如果是，则证明元素扫描完毕，结束循环，如果不是，则交换元素即可
            if(left>=right){
                break;
            }else{
                exch(a,left,right);
            }

        }
        //交换分界值
        exch(a,lo,right);

        return right;
    }

    /**
     * 判断vw
     * @param v
     * @param w
     * @return
     */
    private static boolean less(Comparable v,Comparable w){
        return v.compareTo(w)<0;
    }

    /**
     * 交换a数组中，索引i和索引j处的值
     * @param a
     * @param i
     * @param j
     */
    private static void exch(Comparable[] a,int i,int j){
        Comparable temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    //最优情况下：时间复杂度为O(nlogn);
    //最坏情况下：时间复杂度为O(n^2);
    //平均情况：时间复杂度为O(nlogn);
    public static void main(String[] args) {
        Integer[] array = {6,1,2,7,9,3,4,5,8};
        sort(array);
        System.out.println(Arrays.toString(array));
    }
}
